//题目:
// 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
// 每一对相邻的单词只差一个字母。
// 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
// sk == endWord
// 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。
// 如果不存在这样的转换序列，返回 0 。
#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;
//代码:
class Solution 
{
public:
    bool is_diff_one(const string& s1,const string& s2)
    {
        int cnt=0;
        for(int i=0;i<s1.size();i++)
            if(s1[i]!=s2[i])
                cnt++;
        return cnt==1?true:false;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        //1.用一个哈希表来表征某个单词是否被搜索过
        unordered_map<string,bool> hash;
        for(const auto& str:wordList)hash[str]=false;
        //2.创建一个队列，用于存放所有与某个单词仅相差一个字母的所有单词
        queue<string> q;
        q.push(beginWord);
        hash[beginWord]=true;
        //3.寻找目标单词
        int cnt=1;
        while(!q.empty())
        {
            cnt++;
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                string str=q.front();
                q.pop();
                //遍历worldlist,寻找与str仅相差一个字符的单词
                for(const auto& s:wordList)
                {
                    if(hash[s]==false && is_diff_one(s,str))
                    {
                        if(s==endWord)return cnt;

                        q.push(s);
                        hash[s]=true;
                    }
                }
            }
        }
        return 0;
    }
};